#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int findNumberOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> len(n, 1), count(n, 1);
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (nums[j] < nums[i])
            {
                if (len[j] + 1 == len[i])
                    count[i] += count[j];
                if (len[j] + 1 > len[i])
                {
                    len[i] = len[j] + 1;
                    count[i] = count[j];
                }
            }
        }
    }
    int maxlen = len[0], ret = count[0];
    for (int i = 1; i < n; i++)
    {
        if (len[i] > maxlen) maxlen = len[i], ret = count[i];
        else if (len[i] == maxlen) ret += count[i];
    }
    return ret;
}

int findLongestChain(vector<vector<int>>& pairs) {
    /*sort(pairs.begin(), pairs.end());
    int ret = 1;
    int n = pairs.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (pairs[j][1] < pairs[i][0])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ret = max(ret, dp[i]);
    }
    return ret;*/
    sort(pairs.begin(), pairs.end(), [](const vector<int>& v1, const vector<int>& v2) {
        return v1[1] < v2[1];
        });
    int ret = 0, prev = INT_MIN;
    for (auto x : pairs)
    {
        if (x[0] > prev)
        {
            prev = x[1];
            ret++;
        }
    }
    return ret;
}

int main()
{
	vector<int> v{ 1,3,5,4,7 };
    vector<vector<int>> vv{ {1,2}, {2,3}, {3,4} };
    findNumberOfLIS(v);
    findLongestChain(vv);

	return 0;
}